package leetcode.Hot100;

import java.util.regex.Pattern;

/**
 * @author Cheng Jun
 * Description: 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/regular-expression-matching
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2022/1/3 13:25
 * 困难题
 */
public class isMatch {

    public static void main(String[] args) {

    }

    // 1 <= s.length <= 20
    // 1 <= p.length <= 30
    // s 可能为空，且只包含从 a-z 的小写字母。
    // p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
    // 保证每次出现字符 * 时，前面都匹配到有效的字符
    //
    // 原生工具类
    public boolean isMatch(String s, String p) {
        return Pattern.matches(p, s);
    }

    // 视频题解地址：https://leetcode-cn.com/problems/regular-expression-matching/solution/shi-pin-tu-jie-dong-tai-gui-hua-zheng-ze-biao-da-s/
    // 动态规划状态：dp[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。
    // 动态规划初始化：
    public boolean isMatch1(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean table[][] = new boolean[m + 1][n + 1];
        table[0][0] = true;
        // 初始化table
        for (int col = 1; col < table[0].length; col++) {
            char ch = p.charAt(col - 1);
            if (col > 1) {
                if (ch == '*') {
                    // 出现 * 号的话，取决 前面 col-2 位置是否能匹配上
                    table[0][col] = table[0][col - 2];
                } else {
                    table[0][col] = false;
                }
            } else {
                if (ch == '*') {
                    table[0][col] = true;
                }else {
                    table[0][col] = false;
                }
            }
        }

        for (int row = 1; row < table.length; row++) {
            char ch1 = s.charAt(row - 1);
            for (int col = 1; col < table[row].length; col++) {
                char ch2 = p.charAt(col - 1);
                // 当前 ch1 能和 ch2 匹配上，取决于左上方 table[row - 1][col - 1] 的匹配结果
                if (ch1 == ch2 || ch2 == '.') {
                    table[row][col] = table[row - 1][col - 1];
                } else if (ch2 == '*') {
                    if (col > 1) {
                        if (table[row][col - 2]) {
                            table[row][col] = true; // 前面的字符出现0次
                        } else {
                            char prev = p.charAt(col - 2);
                            if (prev == ch1 || prev == '.') {
                                table[row][col] = table[row - 1][col]; // 前面的字符出现多次
                            }
                        }
                    }
                }
            }
        }
        return table[m][n];
    }
}
